/**
 * @param {string[]} words
 */
 var WordFilter = function(words) {
    this.prefTree = {};
    this.suffTree = {};
    this.buildTree(words);
};

WordFilter.prototype.buildTree = function(words) {
    words.map((word,index)=>{
        let prefTree = this.prefTree;
        let suffTree = this.suffTree;
        for(let i = 0; i < word.length; i++){
            let w = word[i];
            if(!prefTree[w]){
                prefTree[w] = {};
                prefTree[w].list = [];
            }
            prefTree = prefTree[w];
            prefTree.list.push(word);
            w = word[word.length - 1 - i];
            if(!suffTree[w]){
                suffTree[w] = {};
                suffTree[w].map = {};
            }
            suffTree = suffTree[w];
            suffTree.map[word] = index;
        }
    })
};
/** 
 * @param {string} pref 
 * @param {string} suff
 * @return {number}
 */
WordFilter.prototype.f = function(pref, suff) {
    let prefTree = this.prefTree;
    for(const w of pref){
        if(!prefTree[w]) return -1;
        prefTree = prefTree[w];
    }
    let list = prefTree.list;
    let suffTree = this.suffTree;
    suff = suff.split('').reverse().join('');
    for(const w of suff){
        if(!suffTree[w]) return -1;
        suffTree = suffTree[w];
    }
    let map = suffTree.map;
    if(list.length == 0 || !map) return -1;
    for(let i = list.length - 1; i >= 0; i--){
        if(map[list[i]] != undefined) return map[list[i]]; 
    }
    return -1;
};

/**
 * Your WordFilter object will be instantiated and called as such:
 * var obj = new WordFilter(words)
 * var param_1 = obj.f(pref,suff)
 */